#include "sort.h"

void BInsertSort(SqList &L) {
    int i, j;
    for (i = 2; i <= L.length; ++i) {
        L.r[0] = L.r[i];    // 当前插入元素存到"哨兵"位置
        int low = 1; int high = i-1;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (L.r[0].key < L.r[mid].key) high = mid - 1;
            else low = mid + 1;
        }   // 循环结束，high+1则为插入位置
        for (j = i-1; j >= high+1; --j) L.r[j+1] = L.r[j];  // 移动元素
        L.r[high+1]= L.r[0];    // 插入到正确位置
    }
}